1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| #include <cstdio>
#include <ctime>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
const int maxn = 105;
using namespace std;
double x[maxn], y[maxn];
int n, T;
double calc(double xx, double yy){
double res = 0;
for (int i = 1; i <= n; i++){
double dx = xx - x[i], dy = yy - y[i];
res += sqrt(dx * dx + dy * dy);
}
return res;
} double ansx, ansy, ans;
void simulate(){
double x = ansx, y = ansy;
double t = 3000;
while (t > 1e-15){
double X = x + ((rand() << 1) - RAND_MAX) * t;
double Y = y + ((rand() << 1) - RAND_MAX) * t;
double now = calc(X, Y);
double d = now - ans;
if (d < 0){
ansx = X, ansy = Y;
x = X, y = Y;
ans = now;
}
else if (exp(-d / t) * RAND_MAX > rand()) x = X, y = Y;
t *= 0.996;
}
}
int main(){
srand(unsigned(time(0)));
scanf("%d", &n); ansx = 0, ansy = 0;
for (int i = 1; i <= n; i++){
scanf("%lf%lf", x + i, y + i);
ansx += x[i], ansy += y[i];
} ansx /= n, ansy /= n; ans = calc(ansx, ansy);
for (int k = 1; k <= 5; k++) simulate();
printf("%.0lf\n", ans);
return 0;
}
|